package practice;

import struct.BinaryTree;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
 * <p>
 * 由于可能有负数，所以必须遍历到所有叶子节点
 */
public class _112_PathSum {

    /**
     * 112路径和测试
     */
    public static void main(String[] args) {
        BinaryTree root = new BinaryTree(0);
        BinaryTree binaryTree1 = new BinaryTree(1, 2, 3);
        BinaryTree binaryTree2 = new BinaryTree(4, 5, 6);
        binaryTree1.getLeftNode().setRightNode(new BinaryTree(5));
        binaryTree1.getRightNode().setLeftNode(new BinaryTree(6)).setRightNode(new BinaryTree(3));
        binaryTree2.getLeftNode().setRightNode(new BinaryTree(9));
        binaryTree2.getRightNode().setRightNode(new BinaryTree(12));
        root.setLeftNode(binaryTree1).setRightNode(binaryTree2);
        /**
         *
         *               0
         *         1            4
         *     2       3     5     6
         *      5    6   3     9     12
         */

        System.out.println(hasPathSumRecursion(root, 3));
        System.out.println(hasPathSumUnRecursion(root, 1));
    }

    /**
     * 递归实现
     *
     * @param root
     * @param sum
     * @return
     */
    public static boolean hasPathSumRecursion(BinaryTree root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.getLeftNode() == null && root.getRightNode() == null && sum == root.getValue()) {
            return true;
        }
        return hasPathSumRecursion(root.getLeftNode(), sum - root.getValue()) || hasPathSumRecursion(root.getRightNode(), sum - root.getValue());
    }

    /**
     * 非递归实现
     *
     * @param root
     * @param sum
     * @return
     */
    public static boolean hasPathSumUnRecursion(BinaryTree root, int sum) {
        if (root == null) {
            return false;
        }
        Stack<BinaryTree> stack = new Stack<>();
        Set<BinaryTree> set = new HashSet<>();
        BinaryTree node = root;
        int tmpSum = 0;
        while (node != null || !stack.isEmpty()) {
            //向左找到最尾节点
            while (node != null) {
                tmpSum += node.getValue();
                stack.push(node);
                node = node.getLeftNode();
            }
            //和相等
            if (sum == tmpSum || (sum!=tmpSum && !stack.isEmpty())) {
                node = stack.pop();
                //为叶子节点，返回true
                if (node.getLeftNode() == null && node.getRightNode() == null) {
                    return true;
                } else {
                    //不为叶子节点，找到上一个没有遍历过右子树的节点
                    while (set.contains(node)) {
                        //栈为空，所有节点都遍历过，返回false
                        if (stack.isEmpty()) {
                            return false;
                        } else {
                            //回溯
                            tmpSum -= node.getValue();
                            node = stack.pop();
                        }
                    }
                    //找到未遍历过右子树的节点，将该节点放入已遍历过的节点集中，并重新入栈
                    set.add(node);
                    stack.push(node);
                    node = node.getRightNode();
                }
            } else if (stack.isEmpty()) {
                //和不相等，且栈为空，节点都遍历过了，返回false
                return false;
            } else {
                //和相等
                node = stack.pop();
                while (set.contains(node)) {
                    //栈为空，所有节点都遍历过，返回false
                    if (stack.isEmpty()) {
                        return false;
                    } else {
                        //回溯
                        tmpSum -= node.getValue();
                        node = stack.pop();
                    }
                }
                //找到未遍历过右子树的节点，将该节点放入已遍历过的节点集中，并重新入栈
                set.add(node);
                stack.push(node);
                node = node.getRightNode();
            }
        }
        return false;
    }

}
